#include <iostream>
#include <algorithm>
#include <vector>
//shell排序的理解需要先了解插入排序，增加有间隔进行插入排序这个概念，最后的插入间隔是1
//这是利用局部有序对插入排序有时间复杂度降低的作用
//在数据量较大时，shell排序的比较次数会比插入排序少很多
//这里采用的间隔是4，每次二分，但是有很多其它最优的间隔以及分法及方案
void shellSort(std::vector<int> &arr)
{
	int n = arr.size();
	int gap = 4;
	while (gap >= 1)
	{
		//里面直接进行插入排序，不过间隔是gap
		for (int i = gap; i < n; ++i)
		{
			int temp = arr[i];
			int j = i;
			for (; j >= gap && arr[j - gap] > temp; j -= gap)
			{
				arr[j] = arr[j - gap];
			}
			arr[j] = temp;
		}

		gap /= 2;
	}

}

int main()
{
	std::vector<int> arr{3,4,5,3,1,7,8,7,0,13,22,4,1,2,6,7382,33,2231,312312,4341,3131,1231241,1231232,122,3213,132312,3124,5754,7765,32423,4654,234234,23342,345,757,87,980};
	std::vector<int> b;
	b.assign(arr.begin(), arr.end());
	shellSort(arr);
	for (auto i : arr)
	{
	std::cout << i << std::endl;
	}
	std::sort(b.begin(), b.end());
	if (b != arr)
	{
		std::cout << "sort failure!!" << std::endl;
	}
	else
	{
		std::cout << "sort success!!!!" << std::endl;
	}

	return 0;
}